package com.example.algorithm;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

/**
 * 从左到右逐层获取二叉树节点
 *
 * @author huahua
 * @DATE 2024/11/17
 **/
public class LevelOrder {

    public static void main(String[] args) {

    }

    // 定义nextNodeList和curLevelList，每遍历一层，就将当前层节点curList添加到结果res中
    public List<List<Integer>> levelOrderOne(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if(root == null){
            return null;
        }

        // 存储当前层的节点
        List<TreeNode> curList = new ArrayList<>();
        curList.add(root);
        // 每遍历一层，就将当前层节点curList添加到结果res中
        while(!curList.isEmpty()){
            List<TreeNode> nextNodeList = new ArrayList<>();
            List<Integer> curLevelList = new ArrayList<>();
            for(TreeNode node : curList){
                curLevelList.add(node.val);
                if(node.left != null){
                    nextNodeList.add(node.left);
                }
                if(node.right != null){
                    nextNodeList.add(node.right);
                }
            }
            res.add(curLevelList);
            curList = nextNodeList;
        }
        return res;
    }

    /**
     * 建立辅助队列，根节点首先进入队列。不管层次怎么访问，根节点一定是第一个，那它肯定排在队伍的最前面。
     * 每次进入一层，统计队列的元素个数，因为每当访问完一层，下一层作为这一层的子节点，一定都加入队列，而再下一层还没有加入，因此此时队列中的元素个数就是这一层的元素个数。
     * 每次遍历这一层这么多的节点数，将其依次从队列中弹出，然后加入这一行的一维数组中，如果它们有子节点，依次加入队列排队等待访问。
     * 访问完这一层的元素后，将这个一维数组加入二维数组中，再访问下一层。
     */
    public List<List<Integer>> levelOrderTwo(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if(root == null){
            return null;
        }

        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        while(!queue.isEmpty()){
            // 记录二叉树的某一行
            List<Integer> currentRow = new ArrayList();
            int currentQueueSize = queue.size();
            for (int i = 0; i < currentQueueSize; i++) {
                // 先存当前根节点
                TreeNode node = queue.poll();
                currentRow.add(node.val);
                // 若是左右孩子存在，则存入左右孩子作为下一个层次
                if(node.left!= null){
                    queue.add(node.left);
                }
                if(node.right!=null){
                    queue.add(node.right);
                }
            }
            res.add(currentRow);
        }

        return res;
    }


    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
    }
}
